package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * 二叉树的层次遍历
 * Created by Administrator on 2020/1/11.
 */
public class LevelOrder1 {

    public List<List<Integer>> levelOrder(TreeNode root) {

        Map<Integer, List<Integer>> map = new HashMap<>();
        levelOrder(root, 0, map);
        return map.entrySet().stream().sorted((e1,e2) -> e1.getKey().compareTo(e2.getKey())).map(e->e.getValue()).collect(Collectors.toList());
    }

    //BFS
    public List<List<Integer>> levelOrderLists(TreeNode root) {

        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> lists = new ArrayList<>();
        levelOrder(root, 1, lists);
        return lists;
    }

    public void levelOrder(TreeNode root, int level, List<List<Integer>> lists) {
        if (root != null){
            if (lists.size() < level){
                List<Integer> list = new ArrayList<>();
                list.add(root.val);
                lists.add(list);
            }else {
                lists.get(level-1).add(root.val);
            }
            levelOrder(root.left, level+1, lists);
            levelOrder(root.right, level+1, lists);
        }
    }

    public void levelOrder(TreeNode root, int level, Map<Integer, List<Integer>> map) {
        if (root != null){
            List<Integer> list = new ArrayList<>();
            map.compute(level, (k, v) -> {
                if (v == null){
                    list.add(root.val);
                    return list;
                }else {
                    v.add(root.val);
                    return v;
                }
            });
            levelOrder(root.left, level+1, map);
            levelOrder(root.right, level+1, map);
        }
    }

}
